本系列文章同步分享於個人Blog → InformisTry-HankLee

前言

昨天介紹Distribution Sort的時候提到了Map/Dictionary，相信應該很多人對這個物件已經不陌生了，而今天主要是圍繞在Hash Table上面，說明當進行Hashing的時候如果遇到衝突，該怎麼解決？那就讓我們看下去吧～

Hash Table

Hash Table說穿了就是Key-Value Paired Array，，進行Insertion的時候，會依據Key來決定Value要儲存在哪一個位置(index)裡面，而因為Hash Table是Key-Value Paired，在進行Search的時候，永遠都是?(1)的時間複雜度。

假設現在有一組資料，長度為n，要使用Hash Table紀錄這組資料，首先是要找出這組資料的規律，藉此取得屬於每一個值特有的Key，然後再放入Hash Table中，如下範例，當每個值除以10之後，其餘數分別是0, 1, 2,...,8，而利用這個餘數作為key值，如此一來每個值都有一個唯一的Key，並藉此放進Hash Table中。

• Dataset: { 10, 21, 32, 43, 54, 65, 76, 87, 98}
• Key = k(x) = x mod 10
• Keyset : { 0, 1, 2, 3, 4, 5, 6, 7, 8}

但上面這個情況是Hash Table的長度與資料長度相等，倘若現在Hash Table的長度比資料長度小，那絕對就會發生 『衝突』，因此問題來了：如果發生衝突了，該怎麼處理勒？

Separate Chaining Hashing

Separate Chaining Hashing就是針對Hash Table發生衝突時的解決方案之一，其特點為：

1. 允許一個Key值的位置可以存放多個值。
2. 每一個位置都指向(point)一個Linked List，藉此在當中存放多個值。
3. 若某一個位置並無存放任何值，則此時pointer會被設定為null。

範例如下：

從上範例可以看到，16和4兩個值除以12後餘數均為4，1和25除以12餘1，9和33除以12餘9，因此這些值爾後放進Hash Table時被分別放到4, 1, 9的位置下面。

Open Address Hashing

另一種處理衝突的方式是使用Open Address Hashing，這個方法一樣是規定每一個Element只能記錄一個值，但是當遇到衝突的時候，有兩種方式可以用來應對：

1. Linear Probing：

Linear Probing面對衝突的解決方式是針對當前位置去尋找下一個沒放值的Element，並將值存入，先看下面GIF試著了解這句話吧～

可以看到，當要新增10的時候，因為1的位置中已經有值了，因此去找下一個空的位置，才把10放進去；而新增25的時候，從index 7開始，一路找到index 5，才找到空的位置可以存25，這個就是Linear Probing的機制。

2. Double Hashing：

在使用Double Hashing前，基本上會準備兩個hashing function(F1, F2)用來計算，第一次使用F1來計算，當遇到衝突時，則合併兩個hashing function計算，取得新的Primer，依據這個Primer看看是否有衝突，沒有衝突，就把值存入；有衝突，再一次地計算，直到沒衝突為止：

1. 第一次計算：Primer = F1(x)
2. 如果第一點的Primer衝突，則：Primer = F1(x) + F2(x)
3. 若第二點的Primer還是衝突，則：Primer = F1(x) + 2·F2(x)
4. 若第三點的Primer再一次衝突，則：Primer = F1(x) + 3·F2(x)
5. 依此類推，直到不再衝突。

小結

1. Hash Table在Insertion的過程中，若遇到衝突，可以透過Separate Chaining Hashing和Open Address Hashing解決。
2. Separate Chaining Hashing是在每一個Element透過Linked List紀錄多個值。
3. Open Address Hashing又可以分為Linear Probing和Double Hashing兩種方式。
4. Linear Probing是當遇到衝突時，去尋找下一個空的位置存入值。
5. Double Hashing是透過兩個Hashing function來反覆計算Primer，直到沒有衝突為止。

預告

明天開始的一年三天，我們將會介紹Dynamic Programming這個類別的演算法。

References

1. Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin